/**
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 
 * 输入: amount = 5, coins = [1, 2, 5]
 * 输出: 4 
 **/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


// 动态规划
// TODO:
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int dp[coins.size()+1][amount+1];
        for(int i=0; i<coins.size()+1;i++){
            for(int j=0; j<amount+1; j++){
                dp[i][j] = 0;
            }
        }

        // 总金额为0时，有什么都不取这一种方法
        for(int k=0; k<=coins.size(); k++){
            dp[k][0] = 1;
        }

        for(int i=1; i<=coins.size(); i++){
            for(int j=1; j<=amount; j++){
                if(j >= coins[i-1]){
                    dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[coins.size()][amount];
    }
};

int main(){
    vector<int> coins = {1, 2, 5};
    int amount = 5;
    Solution s;
    int result = s.change(amount, coins);
    cout<<result;
}